/*
Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

Only one letter can be changed at a time
Each intermediate word must exist in the dictionary
For example,

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note:
Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.
*/

class Solution {
public:
    int ladderLength(string start, string end, unordered_set<string> &dict) {
        int level = 0;
        unordered_set<string> vset;
        queue<string> wqueue, wqueue_next;
        wqueue.push(start);
        while (!wqueue.empty()) {
            level++;
            while (!wqueue.empty()) {
                string &word = wqueue.front();
                // generate words based on word
                for (int i = 0; i < word.length(); i++) {
                    char tmp = word[i];
                    for (char c = 'a'; c <= 'z'; c++) {
                        if (c != word[i]) {
                            word[i] = c;
                            if (word == end) { return (level+1); }
                            if (dict.find(word) != dict.end() && vset.find(word) == vset.end()) {
                                vset.insert(word); wqueue_next.push(word); // found new word
                            }
                            word[i] = tmp;
                        }
                    }
                }
                wqueue.pop(); // go to next word
            }
            swap(wqueue, wqueue_next);
        }
        return 0;
    }
};
